{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Different Subsequences GCDs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #counting #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #计数 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countDifferentSubsequenceGCDs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #序列中不同最大公约数的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由正整数组成的数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>数字序列的 <strong>最大公约数</strong> 定义为序列中所有整数的共有约数中的最大整数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，序列 <code>[4,6,16]</code> 的最大公约数是 <code>2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>数组的一个 <strong>子序列</strong> 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[2,5,10]</code> 是 <code>[1,2,1,<strong>2</strong>,4,1,<strong>5</strong>,<strong>10</strong>]</code> 的一个子序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>计算并返回 <code>nums</code> 的所有 <strong>非空</strong> 子序列中 <strong>不同</strong> 最大公约数的 <strong>数目</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/04/03/image-1.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [6,10,3]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>上图显示了所有的非空子序列与各自的最大公约数。\n",
    "不同的最大公约数为 6 、10 、3 、2 和 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,15,40,5,6]\n",
    "<strong>输出：</strong>7\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 2 * 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-different-subsequences-gcds](https://leetcode.cn/problems/number-of-different-subsequences-gcds/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-different-subsequences-gcds](https://leetcode.cn/problems/number-of-different-subsequences-gcds/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,10,3]', '[5,15,40,5,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        maxVal = max(nums)\n",
    "        occured = [False] * (maxVal + 1)\n",
    "        for num in nums:\n",
    "            occured[num] = True\n",
    "        ans = 0\n",
    "        for i in range(1, maxVal + 1):\n",
    "            subGcd = 0\n",
    "            for j in range(i, maxVal + 1, i):\n",
    "                if occured[j]:\n",
    "                    if subGcd == 0:\n",
    "                        subGcd = j\n",
    "                    else:\n",
    "                        subGcd = gcd(subGcd, j)\n",
    "                    if subGcd == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        \"\"\"计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。\"\"\"\n",
    "        max_ = max(nums)\n",
    "        has = [False] * (max_ + 1)\n",
    "        for num in nums:\n",
    "            has[num] = True\n",
    "\n",
    "        # 枚举答案\n",
    "        res = 0\n",
    "        for i in range(1, max_ + 1):\n",
    "            gcd_ = 0\n",
    "            for j in range(i, max_ + 1, i):\n",
    "                if has[j]:\n",
    "                    gcd_ = gcd(gcd_, j)\n",
    "                    if gcd_ == i:\n",
    "                        res += 1\n",
    "                        break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        maxv = max(nums)\n",
    "        g = [False] * (maxv + 1)\n",
    "        for num in nums:\n",
    "            g[num] = True\n",
    "        ans = 0\n",
    "        for i in range(1, maxv + 1):\n",
    "            tmp = 0\n",
    "            for j in range(i, maxv + 1, i):\n",
    "                if g[j]:\n",
    "                    tmp = j if tmp == 0 else math.gcd(tmp, j)\n",
    "                    if tmp == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        mx = max(nums)\n",
    "        s = [False] * (mx + 1)\n",
    "        for num in nums:\n",
    "            s[num] = True\n",
    "        ans = 0\n",
    "        for num in range(mx, 0, -1):\n",
    "            if s[num]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                g = None\n",
    "                for j in range(num, mx + 1, num):\n",
    "                    if s[j]:\n",
    "                        if not g:\n",
    "                            g = j\n",
    "                        else:\n",
    "                            g = gcd(g, j)\n",
    "                    if g == num:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        maxVal = max(nums)\n",
    "        occured = [False] * (maxVal + 1)\n",
    "        for num in nums:\n",
    "            occured[num] = True\n",
    "        ans = 0\n",
    "        for i in range(1, maxVal + 1):\n",
    "            subGcd = 0\n",
    "            for j in range(i, maxVal + 1, i):\n",
    "                if occured[j]:\n",
    "                    if subGcd == 0:\n",
    "                        subGcd = j\n",
    "                    else:\n",
    "                        subGcd = gcd(subGcd, j)\n",
    "                    if subGcd == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        ans, mx = 0, max(nums)\n",
    "        has = [False] * (mx + 1)\n",
    "        for x in nums:\n",
    "            if not has[x]:\n",
    "                has[x] = True\n",
    "                ans += 1 # 单独一个树也算\n",
    "        for i in range(1, mx // 3 + 1): #优化循环上界\n",
    "            if has[i]: continue \n",
    "            g = 0 # 0 和 任何数x的最大公约数都是x\n",
    "            for j in range(i * 2, mx + 1, i): # 枚举i的倍数j\n",
    "                if has[j]: # 如果j在nums中\n",
    "                    g = gcd(g, j)\n",
    "                    if g == i: # 跟新最大公约数\n",
    "                        ans += 1\n",
    "                        break # 提前退出循环\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        ans, mx = 0, max(nums)\n",
    "        has = [False] * (mx + 1)\n",
    "        for x in nums: has[x] = True\n",
    "        for i in range(1, mx + 1):\n",
    "            g = 0  \n",
    "            for j in range(i, mx + 1, i): \n",
    "                if has[j]: \n",
    "                    g = gcd(g, j) \n",
    "                    if g == i:  \n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# MX = 2 * 10 ** 5 + 1\n",
    "# primes = []\n",
    "# is_primes = [True] * MX\n",
    "# for num in range(2, MX):\n",
    "#     if is_primes[num]:\n",
    "#         primes.append(num)\n",
    "#         is_primes[num] = False\n",
    "#         for j in range(num * 2, MX, num):\n",
    "#             is_primes[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        \n",
    "\n",
    "        mx = max(nums)\n",
    "        s = [False] * (mx + 1)\n",
    "        g = nums[0]\n",
    "        for num in nums:\n",
    "            s[num] = True\n",
    "        ans = 0\n",
    "        for num in range(mx, 0, -1):\n",
    "            if s[num]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                g = None\n",
    "                # j = 2\n",
    "                for j in range(num * 2, mx + 1, num):\n",
    "                    if s[j]:\n",
    "                        if not g:\n",
    "                            g = j // num\n",
    "                        else:\n",
    "                            g = gcd(g, j // num)\n",
    "                if g == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# MX = 2 * 10 ** 5 + 1\n",
    "# primes = []\n",
    "# is_primes = [True] * MX\n",
    "# for num in range(2, MX):\n",
    "#     if is_primes[num]:\n",
    "#         primes.append(num)\n",
    "#         is_primes[num] = False\n",
    "#         for j in range(num * 2, MX, num):\n",
    "#             is_primes[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        \n",
    "\n",
    "        mx = max(nums)\n",
    "        s = [False] * (mx + 1)\n",
    "        g = nums[0]\n",
    "        for num in nums:\n",
    "            g = gcd(g, num)\n",
    "            s[num] = True\n",
    "        ans = int(g == 1)\n",
    "        for num in range(mx, 1, -1):\n",
    "            if s[num]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                g = None\n",
    "                # j = 2\n",
    "                for j in range(num * 2, mx + 1, num):\n",
    "                    if s[j]:\n",
    "                        if not g:\n",
    "                            g = j // num\n",
    "                        else:\n",
    "                            g = gcd(g, j // num)\n",
    "                if g == 1:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        maxVal = max(nums)\n",
    "        occured = [False] * (maxVal + 1)\n",
    "        for num in nums:\n",
    "            occured[num] = True\n",
    "        ans = 0\n",
    "        for i in range(1, maxVal + 1):\n",
    "            subGcd = 0\n",
    "            for j in range(i, maxVal + 1, i):\n",
    "                if occured[j] == True:\n",
    "                    if subGcd == 0:\n",
    "                        subGcd = j\n",
    "                    else:\n",
    "                        subGcd = gcd(subGcd, j)\n",
    "                    if subGcd == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        ans, mx = 0, max(nums)\n",
    "        has = [False] * (mx + 1)\n",
    "        for x in nums:\n",
    "            has[x] = True\n",
    "        for i in range(1, mx + 1):\n",
    "            g = 0  \n",
    "            for j in range(i, mx + 1, i): \n",
    "                if has[j]: \n",
    "                    g = gcd(g, j) \n",
    "                    if g == i:  \n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        result, visited = 0, [False] * ((m := max(nums)) + 1)\n",
    "        for num in nums:\n",
    "            visited[num] = True\n",
    "        for i in range(1, m + 1):\n",
    "            cur = 0\n",
    "            for j in range(i, m + 1, i):\n",
    "                if visited[j]:\n",
    "                    if (cur := gcd(cur, j)) == i:\n",
    "                        break\n",
    "            result += cur == i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        ans, mx = 0, max(nums)\n",
    "        has = [False] * (mx + 1)\n",
    "        for x in nums: has[x] = True\n",
    "        for i in range(1, mx + 1):\n",
    "            g = 0  # 0 和任何数 x 的最大公约数都是 x\n",
    "            for j in range(i, mx + 1, i):  # 枚举 i 的倍数 j\n",
    "                if has[j]:  # 如果 j 在 nums 中\n",
    "                    g = gcd(g, j)  # 更新最大公约数\n",
    "                    if g == i:  # 找到一个答案（g 无法继续减小）\n",
    "                        ans += 1\n",
    "                        break  # 提前退出循环\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        maxv = max(nums)\n",
    "        g = [False] * (maxv + 1)\n",
    "        for num in nums:\n",
    "            g[num] = True\n",
    "        ans = 0\n",
    "        for i in range(1, maxv + 1):\n",
    "            tmp = 0\n",
    "            for j in range(i, maxv + 1, i):\n",
    "                if g[j]:\n",
    "                    tmp = j if tmp == 0 else math.gcd(tmp, j)\n",
    "            if tmp == i:\n",
    "                ans += 1\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        def GCD(a, b):\n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        count = 0\n",
    "        m = max(nums) + 1\n",
    "        exist = [False] * m\n",
    "        for x in nums:\n",
    "            exist[x] = True\n",
    "        for i in range(1, m):\n",
    "            gcd = 0\n",
    "            for j in range(i, m, i):\n",
    "                if exist[j]:\n",
    "                    gcd = GCD(j, gcd)\n",
    "                    if gcd == i:\n",
    "                        count += 1\n",
    "                        break\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        maxVal = max(nums)\n",
    "        occured = [False] * (maxVal + 1)\n",
    "        for num in nums:\n",
    "            occured[num] = True\n",
    "        ans = 0\n",
    "        for i in range(1, maxVal + 1):\n",
    "            subGcd = 0\n",
    "            for j in range(i, maxVal + 1, i):\n",
    "                if occured[j]:\n",
    "                    if subGcd == 0:\n",
    "                        subGcd = j\n",
    "                    else:\n",
    "                        subGcd = gcd(subGcd, j)\n",
    "                    if subGcd == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        def check(x, hashtable, m):\n",
    "            cgcd = 0\n",
    "            for i in range(x, m+1, x):\n",
    "                if hashtable[i]:\n",
    "                    if cgcd == 0: cgcd = i\n",
    "                    else: cgcd = gcd(cgcd, i)\n",
    "                    if cgcd == x: return True\n",
    "            return False\n",
    "\n",
    "        m = max(nums)\n",
    "        hashtable = [False for _ in range(m+1)]\n",
    "        for i in range(len(nums)): hashtable[nums[i]] = True\n",
    "        amount = 0\n",
    "        for i in range(1, m+1):\n",
    "            if check(i, hashtable, m):\n",
    "                amount += 1\n",
    "        return amount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        mx = max(nums)+1\n",
    "        gc = [False] * (mx)\n",
    "        r = 0\n",
    "        for x in nums:\n",
    "            gc[x] = True\n",
    "        for i in range(1,mx):\n",
    "            g = 0\n",
    "            for j in range(i,mx,i):\n",
    "                if gc[j]:\n",
    "                    g = gcd(g,j)\n",
    "                if g == i: \n",
    "                    r+=1\n",
    "                    break\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def gcd(nums1, nums2) -> int:\n",
    "        if nums1 > nums2:\n",
    "            smaller = nums2\n",
    "        else:\n",
    "            smaller = nums1\n",
    "        \n",
    "        for i in range(1,smaller +1):\n",
    "            if((i % nums1 == 0) and (i % nums2 == 0)):\n",
    "                gcd = i\n",
    "        return gcd\n",
    "\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        ans, mx = 0, max(nums)\n",
    "        has = [False] * (mx + 1)\n",
    "        for x in nums:\n",
    "            if not has[x]:\n",
    "                has[x] = True\n",
    "                ans += 1\n",
    "\n",
    "        for i in range(1 , mx // 3 + 1):\n",
    "            if has[i]: continue\n",
    "            g = 0\n",
    "            for j in range(i* 2, mx + 1,i):\n",
    "                if has[j]:\n",
    "                    g = gcd(g,j)\n",
    "                    if g == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        #copy zero\n",
    "\n",
    "        nums = set(nums)\n",
    "        c= max(nums)\n",
    "        ans = 0\n",
    "\n",
    "        for y in range(1,c+1):\n",
    "            g = None\n",
    "            for x in range(y,c+1,y):\n",
    "                if x in nums:\n",
    "                    if not g:\n",
    "                        g =x\n",
    "                    else:\n",
    "                        g = math.gcd(g,x)\n",
    "                    if g == y:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        maxVal = max(nums)\n",
    "        occur = set()\n",
    "        for num in nums:\n",
    "            occur.add(num)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, maxVal + 1):\n",
    "            curGcd = 0\n",
    "            for j in range(i, maxVal + 1, i):\n",
    "                if j in occur:\n",
    "                    if curGcd == 0:\n",
    "                        curGcd = j\n",
    "                    else:\n",
    "                        curGcd = gcd(curGcd, j)\n",
    "                    if curGcd == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# MX = 2 * 10 ** 5 + 1\n",
    "# primes = []\n",
    "# is_primes = [True] * MX\n",
    "# for num in range(2, MX):\n",
    "#     if is_primes[num]:\n",
    "#         primes.append(num)\n",
    "#         is_primes[num] = False\n",
    "#         for j in range(num * 2, MX, num):\n",
    "#             is_primes[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "\n",
    "        s = set(nums)\n",
    "        g = nums[0]\n",
    "        for num in s:\n",
    "            g = gcd(g, num)\n",
    "        mx = max(nums)\n",
    "        ans = int(g == 1)\n",
    "        # t = []\n",
    "        for num in range(mx, 1, -1):\n",
    "            if num in s:\n",
    "                ans += 1\n",
    "                # t.append(num)\n",
    "            else:\n",
    "                g = None\n",
    "                # j = 2\n",
    "                for j in range(num * 2, mx + 1, num):\n",
    "                    if j in s:\n",
    "                        if not g:\n",
    "                            g = j // num\n",
    "                        else:\n",
    "                            g = gcd(g, j // num)\n",
    "                if g == 1:\n",
    "                    ans += 1\n",
    "                    # t.append(num)\n",
    "        # print(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        ma = max(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, ma + 1):\n",
    "            g = 0\n",
    "            for j in range(i, ma + 1, i):\n",
    "                if j in nums:\n",
    "                    g = gcd(g, j)\n",
    "                    if g == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        c = max(nums)\n",
    "        ans = 0\n",
    "\n",
    "        for y in range(1, c + 1):\n",
    "            g = None\n",
    "            for x in range(y, c + 1, y):\n",
    "                if x in nums:\n",
    "                    if not g:\n",
    "                        g = x\n",
    "                    else:\n",
    "                        g = math.gcd(g, x)\n",
    "                    if g == y:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        ma = max(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, ma + 1):\n",
    "            g = 0\n",
    "            for j in range(i, ma + 1, i):\n",
    "                if j in nums:\n",
    "                    g = j if not g else gcd(g, j)\n",
    "                    if g == i:\n",
    "                        ans += 1\n",
    "                        break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# MX = 2 * 10 ** 5 + 1\n",
    "# primes = []\n",
    "# is_primes = [True] * MX\n",
    "# for num in range(2, MX):\n",
    "#     if is_primes[num]:\n",
    "#         primes.append(num)\n",
    "#         is_primes[num] = False\n",
    "#         for j in range(num * 2, MX, num):\n",
    "#             is_primes[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "\n",
    "        s = set(nums)\n",
    "        g = nums[0]\n",
    "        for num in s:\n",
    "            g = gcd(g, num)\n",
    "        mx = max(nums)\n",
    "        ans = int(g == 1)\n",
    "        # t = []\n",
    "        for num in range(mx, 1, -1):\n",
    "            if num in s:\n",
    "                ans += 1\n",
    "                # t.append(num)\n",
    "            else:\n",
    "                g = None\n",
    "                j = 2\n",
    "                while num * j <= mx:\n",
    "                    if num * j in s:\n",
    "                        if not g:\n",
    "                            g = j\n",
    "                        else:\n",
    "                            g = gcd(g, j)\n",
    "                    j += 1\n",
    "                if g == 1:\n",
    "                    ans += 1\n",
    "                    # t.append(num)\n",
    "        # print(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        v = set(nums)\n",
    "        ans = 0\n",
    "        mx = max(nums)\n",
    "        # 因数遍历\n",
    "        for i in range(1,mx + 1):\n",
    "            f = 0\n",
    "            cur = i\n",
    "            # 如果该因子存在于数组\n",
    "            if cur in v:\n",
    "                ans += 1\n",
    "                continue\n",
    "            p = -1\n",
    "            while p != 1 and cur + i <= mx:\n",
    "                cur += i\n",
    "                if cur in v:\n",
    "                    if p == -1:\n",
    "                        p = cur // i\n",
    "                    else:\n",
    "                        p = math.gcd(p,cur // i)\n",
    "            if p == 1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "        v = set(nums)\n",
    "        ans = 0\n",
    "        mx = max(nums)\n",
    "        for i in range(1,mx + 1):\n",
    "            f = 0\n",
    "            cur = i\n",
    "            if cur in v:\n",
    "                ans += 1\n",
    "                continue\n",
    "            p = -1\n",
    "            while p != 1 and cur + i <= mx:\n",
    "                cur += i\n",
    "                if cur in v:\n",
    "                    \n",
    "                    if p == -1:\n",
    "                        p = cur // i\n",
    "                    else:\n",
    "                        p = math.gcd(p,cur // i)\n",
    "            if p == 1:\n",
    "                #print(i)\n",
    "                ans += 1\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# MX = 2 * 10 ** 5 + 1\n",
    "# primes = []\n",
    "# is_primes = [True] * MX\n",
    "# for num in range(2, MX):\n",
    "#     if is_primes[num]:\n",
    "#         primes.append(num)\n",
    "#         is_primes[num] = False\n",
    "#         for j in range(num * 2, MX, num):\n",
    "#             is_primes[j] = False\n",
    "\n",
    "class Solution:\n",
    "    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:\n",
    "\n",
    "        s = set(nums)\n",
    "        g = nums[0]\n",
    "        for num in s:\n",
    "            g = gcd(g, num)\n",
    "        mx = max(nums)\n",
    "        ans = int(g == 1)\n",
    "        # t = []\n",
    "        for num in range(mx, 1, -1):\n",
    "            if num in s:\n",
    "                ans += 1\n",
    "                # t.append(num)\n",
    "            else:\n",
    "                g = None\n",
    "                # j = 2\n",
    "                for j in range(num * 2, mx + 1, num):\n",
    "                    if j in s:\n",
    "                        if not g:\n",
    "                            g = j // num\n",
    "                        else:\n",
    "                            g = gcd(g, j // num)\n",
    "                if g == 1:\n",
    "                    ans += 1\n",
    "                    # t.append(num)\n",
    "        # print(t)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
